package leetcode.templates.unions;

import java.util.HashMap;
import java.util.Map;

public class UnionMap {
	Map<Integer, Integer> p;

	public void init() {
		p = new HashMap<>();
	}

	public void union(int a, int b) {
		p.put(find(a), find(b));
	}

	public int find(int id) {
		if (!p.containsKey(id)) {
			p.put(id, id);
		}
		if (p.get(id) != id) {
			p.put(id, this.find(p.get(id)));
		}
		return p.get(id);
	}

	public boolean isSameSet(int a, int b) {
		return find(a) == find(b);
	}
}
